We show how to use the branch-and-bound design strategy by applying it to the 0-1 Knapsack problem. First we discuss a simple version called breadth-first search with branch-and-bound pruning. After that, we show an improvement on the simple version called best-first search with branch-and-bound pruning.

0-1 배낭 문제에 너비우선탐색을 적용해봄으로써 분기한정기법을 어떻게 사용하는지 살펴볼 것이다. 그 후 동 문제에 최고우선탐색까지 적용할 것이다(너비우선탐색을 조금 변형하면 최고우선탐색이 되기 때문).

Example Suppose that n = 4, W = 16, and we have the following:

각 노드에는 3가지 값들이 들어가 있는데 제일 위부터 profit, weight, bound 값이다. 하늘색으로 칠해진 노드가 최적의 해답을 보유한 노드이다. 백트래킹에서 본 것과 비슷하지만 상태공간트리를 방문하는 순서가 너비우선탐색이다. 예를 들어 백트래킹기법에서는 노드(1, 2)가 유망하지 않음을 알았고 그 아래로 확장하지 않았다. 하지만 너비우선탐색을 통한 분기한정법에서는 노드(1,2)아래로 확장한다.

The Breadth-First Search with Branch-and-Bound Pruning Algorithm for the 0-1 Knapsack Problem

Algorithm Design

Using breadth-first search with branch-and-bound pruning, we proceed exactly as we did using backtracking, except that we do a breadth-first search instead of a depth-first search. That is, we let weightand profit be the total weight and total profit of the items that have been included up to a node.

Unlike depth-first search, there is no simple recursive algorithm for breadth-first search. However, we can implement it using a queue. The algorithm that follows does this. The algorithm is written specifically for trees because presently we are interested only in trees. We insert an item at the end of the queue with a procedure called enqueue, and we remove an item from the front with a procedure called dequeue.

Notice that nodes (3, 1) and (4, 3) have bounds of 0. A branch-and-bound algorithm decides whether to expand beyond a node by checking whether its bound is better than the value of the best solution found so far. Therefore, when a node is nonpromising because its weight is not less than W, we set its bound to 0. In this way, we ensure that its bound cannot be better than the value of the best solution found so far.

0-1 배낭 문제에 분기한정 가지치기 너비우선탐색을 사용하면 깊이우선탐색 대신 너비우선탐색을 하게 된다. 너비우선탐색은 깊이우선탐색과 달리 재귀 알고리즘을 사용하지 않으며, 그 대신 큐(queue) 자료구조를 사용하여 알고리즘을 구현한다. 이런 점을 제외하면 백트래킹에서 봤던 방법과 똑같은 방법으로 진행된다.

분기한정 알고리즘은 노드의 확장 여부를 결정할 때, 자식노드로 확장했을 때의 bound 값이 현재까지 구한 가장 좋은 답보다 더 큰지 검사한다. 여기서 weight가 W를 초과하여 해당 노드가 유망하지 않게 되면 노드(3, 1), (4, 3) 처럼 bound를 0으로 설정한다.

Last of all, in a simple breadth-first search with branch-and-bound pruning, the decision of whether or not to visit a node’s children is made at the time the node is visited. That is, if the branches to the children are pruned, they are pruned when the node is visited. Therefore, when we visit node (2, 3), we decide to visit its children because the value of maxprofit at that time is only 70, whereas the bound for the node is 82. Unlike a depth-first search, in a breadth-first search the value of maxprofit can change by the time we actually visit the children. In this case, maxprofit has a value of 90 by the time we visit the children of node (2, 3). We then waste our time checking these children. We avoid this in our best-first search, which is described in the next subsection.

마지막으로 분기한정 가지치기 너비우선탐색은 어떤 노드의 자식노드를 방문해야 할지는 그 노드를 방문할 때 결정한다. 깊이우선탐색과는 달리 너비우선탐색에서는 maxprofit의 값이 자식노드를 실제 방문하는 때에 변할 수 있다.

To determine whether the node is promising, we initialize totweight and bound to weight and profit, respectively, and then greedily grab items, adding their weights and profits to totweight and bound, until we reach an item whose weight would bring totweight above W . We grab the fraction of that item allowed by the available weight, and add the profit of that fraction to bound. In this way, bound becomes an upper bound on the amount of profit we could obtain by expanding beyond the node. If the node is at level i, and the node at level k is the one whose weight would bring the weight above W , then

$$
\begin{align}
totweight &= weight + \sum_{j=i+1}^{k-1}w_j \\
bound &= \left(profit + \sum_{j=i+1}^{k-1}p_j\right) + (W - totweight) \times \frac{w_k}{p_k}
\end{align}
$$

• profit: the sum of the profits of the items included up to the node.
• weight: the sum of the weights of those items.
• totweight: the sum of the weights could be obtained by expanding beyond that node (W를 초과할 수 없다.)
• bound: the upper bound on the profit that could be obtained by expanding beyond that node.

Recall that a node is also nonpromising if

$$
weight <= W
$$

Pseudo Code

void knapsack2(int n, const int p[], cont int w[], int W, int& maxprofit)
{
  queue_of_node Q;   
  node u, v;   

  initialize(Q); // Initialize Q to be empty.
  v.level =0; v.profit = 0; v.weight = 0; // Initialize v to be the root.

  maxprofit = 0;
  enqueue(Q, v);    
  while (!empty(Q)) {
    dequeue(Q, v);  
    u.level = v.level+1; // Set u to a child of v.            
    u.profit = v.profit + p[u.level]; // Set u to the child that
    u.weight = v.weight + w[u.level]; // includes the next item.

    if ((u.weight <= W) && (u.profit > maxprofit))
        maxprofit = u.profit;
    if (bound(u) > maxprofit)  
        enqueue(Q, u);
    u.weight = v.weight; // Set u to the child that does not
    u.profit = v.profit; // does not include the next item.  
    if (bound(u) > maxprofit)  
        enqueue(Q, u);
  }
}

Source Code

// File: knapsack_bfs.h

namespace algorithms
{
  struct node
  {
    int level; // the node's level in the tree
    int profit;
    int weight;
  };
  typedef struct node node;

  void knapsack2(int n, const int p[ ], const int w[ ], int W, int& maxprofit);
  // Problem: Let n items be given, where each item has a weight and
  // a profit. The weights and profits are positive integers. Furthermore,
  // let a positive integer W be given. Determine a set of items with
  // maximum total profit, under the constraint that the sum of their
  // weights cannot exceed W .
  // Inputs: positive integers n and W , arrays of positive integers
  // w and p, each indexed from 1 to n, and each of which is sorted in
  // nonincreasing order according to the values of p[i] / w [i].
  // Outputs: an integer maxprofit that is the sum of the profits in an
  // optimal set.

  float bound(node u, int n, const int p[ ], const int w[ ], int W);
}

// File: knapsack_bfs.cpp
#include <cassert> // Provides assert
#include <queue> // Provides queue
#include <iostream>
#include <iomanip>
#include "knapsack_bfs.h"
using namespace std;

namespace algorithms
{
  void knapsack2(int n, const int p[ ], const int w[ ], int W, int& maxprofit)
  {
    queue<node> Q;
    node u, v;
    int depth = 1;
    int prm_node_cnt = 0; // The number of promising nodes
    int nprm_node_cnt = 0; // The number of non-promising nodes

    assert(Q.empty( )); // Initialize Q to be empty.
    // Initialize v to be the root.
    v.level = 0;
    v.profit = 0;
    v.weight = 0;
    maxprofit = 0;
    Q.push(v); // enqueue(Q, v)

    while(!Q.empty( ))
    {
      v = Q.front( );
      cout << "level: " << setw(2) << v.level;
      cout << "  profit: " << setw(2) << v.profit;
      cout << "  weight: " << setw(2) << v.weight << endl;

      Q.pop( ); // dequeue(Q, v)
      u.level = v.level + 1; // Set u to a child of v.
      u.profit = v.profit + p[u.level]; // Set u to the child that
      u.weight = v.weight + w[u.level]; // includes the next item.

      if (u.weight <= W && u.profit > maxprofit)
        maxprofit = u.profit;

      if (bound(u, n, p, w, W) > maxprofit)
      {
        Q.push(u); // enqueue(Q, u)
        ++prm_node_cnt; // Count the number of promising nodes
      }
      else
      {
        // Count the number of non-promising nodes
        ++nprm_node_cnt;
      }

      u.profit = v.profit; // Set u to the child that does
      u.weight = v.weight; // not include the next item.

      if (bound(u, n, p, w, W) > maxprofit)
      {
        Q.push(u); // enqueue(Q, u)
        ++prm_node_cnt; // Count the number of promising nodes
      }
      else
      {
        // Count the number of non-promising nodes
        ++nprm_node_cnt;
      }
    }

    cout << endl;
    cout << "The num of promising nodes: " << prm_node_cnt+1 << endl;
    cout << "The num of non-promising nodes: " << nprm_node_cnt << endl;
  }

  float bound(node u, int n, const int p[ ], const int w[ ], int W)
  {
    int j, k;
    int totweight;
    float result;

    if (u.weight >= W)
      return 0;
    else
    {
      result = (float)u.profit;
      j = u.level + 1;
      totweight = u.weight;

      while (j <= n && totweight + w[j] <= W)
      {
        // Grab as many items as possible.
        totweight = totweight + w[j];
        result = result + p[j];
        ++j;
      }  
      k = j; // Use k for consistency with formula in text.

      if (k <= n) // Grab fraction of kth item.
        result = result + (W - totweight) * (p[k] / w[k]);

      return result;
    }
  }
}

// File:  maxtotprofit.cpp
#include <iostream>
#include <cstdlib>
#include <ctime>
#include "knapsack_bfs.h"
using namespace std;
using namespace algorithms;

int main( )
{
  // CONSTANT and VARIANCES
  const int n = 4;
  const int W = 16;
  int w[n+1] = {0, 2, 5, 10, 5}; // w[0] is meaningless
  int p[n+1] = {0, 40, 30, 50, 10}; // p[0] is meaningless
  int maxprofit = 0;
  clock_t start, end;

  start = clock( );
  knapsack2(n, p, w, W, maxprofit);
  end = clock( );

  cout << "The answer: $" << maxprofit << endl;
  double result = (double)(end-start) / CLOCKS_PER_SEC;
  cout << "Elpased time is: "<< result << " sec." << endl;

  return EXIT_SUCCESS;
}

Time Complexity Analysis

Worst-Case Time Complexity

• $O(n) = 1 + 2 + 2^2 + 2^3 + … + 2^n = 2^{(n+1)} - 1 \in \Theta(2^n)$

$w_i$를 포함시키느냐 그렇지 않느냐의 두 가지 선택이므로 상태공간트리 내 전체 노드의 수는 최대 $2^{n+1} - 1$개가 된다. 최악의 경우 방문하는 노드의 수가 지수이지만, 가지치기를 통해 상태노드의 수를 줄일 수 있기 때문에 알고리즘의 효율은 더 좋을 수 있다.

Comparing the Algorithm Techniques for the 0-1 Knapsack Problem

Owing to the additional bound of nW , it may appear that the dynamic programming algorithm is superior. However, in backtracking algorithms the worst case gives little insight into how much checking is usually saved by backtracking. In general, the breadth-first search strategy has no advantage over a depth-first search(backtracking).

일반적으로 0-1 배낭 문제에 대해 너비우선탐색의 효율이 깊이우선탐색(백트래킹)보다 더 좋다고 단정지을 순 없다. 깊이우선탐색과 너비우선탐색 중 무엇이 더 효율적이냐에 대한 답은 문제마다 다르기 때문이다.

nW 덕분에 동적계획 알고리즘으로 문제를 해결하는게 더 좋은 것처럼 보일 수 있다. 그러나 백트래킹, 너비우선탐색 알고리즘에서 최악의 경우를 따지면 실제 방문하는 노드의 수를 얼마나 절약했는지 반영이 안되므로, 알고리즘의 상대적인 효율을 이론적으로 분석하기는 어렵다.